Search for: All records

Longest Increasing Subsequence (LIS) is a fundamental problem in combinatorics and computer science. Previously, there have been numerous works on both upper bounds and lower bounds of the time complexity of computing and approximating , yet only a few on the equally important space complexity. In this paper, we further study the space complexity of computing and approximating LIS in various models. Specifically, we prove non-trivial space lower bounds in the following two models: (1) the adaptive query-once model or read-once branching programs, and (2) the streaming model where the order of streaming is different from the natural order. As far as we know, there are no previous works on the space complexity of LIS in these models. Besides the bounds, our work also leaves many intriguing open problems. 

Altered tissue mechanics is an important signature of invasive solid tumors. While the phenomena have been extensively studied by measuring the bulk rheology of the extracellular matrix (ECM) surrounding tumors, micromechanical remodeling at the cellular scale remains poorly understood. By combining holographic optical tweezers and confocal microscopy on in vitro tumor models, we show that the micromechanics of collagen ECM surrounding an invading tumor demonstrate directional anisotropy, spatial heterogeneity and significant variations in time as tumors invade. To test the cellular mechanisms of ECM micromechanical remodeling, we construct a simple computational model and verify its predictions with experiments. We find that collective force generation of a tumor stiffens the ECM and leads to anisotropic local mechanics such that the extension direction is more rigid than the compression direction. ECM degradation by cell-secreted matrix metalloproteinase softens the ECM, and active traction forces from individual disseminated cells re-stiffen the matrix. Together, these results identify plausible biophysical mechanisms responsible for the remodeled ECM micromechanics surrounding an invading tumor. 

Understanding the mechanisms governing biological invasions has implications for population dynamics, biodiversity, and community assembly. The enemy escape hypothesis posits that escape from enemies such as herbivores and predators that were limiting in the native range helps explain rapid spread in the introduced range. While the enemy escape hypothesis has been widely tested aboveground, data limitations have prevented comparisons of belowground mechanisms for invasive and noninvasive introduced species, which limits our understanding of why only some introduced species become invasive. We assessed the role of soil biota in driving plant invasions in a phylogenetic meta−analysis, incorporating phylogeny in the error structure of the models, and comparing live and sterilized conditioned soils. We found 29 studies and 396 effect size estimates across 103 species that compared live and sterilized soils. We found general positive effects of soil biota for plants (0.099, 95% CI = 0.0266, 0.1714), consistent with a role of soil mutualists. The effect size of soil biota among invaders was 3.2× higher than for natives, the strength of effects was weaker for older conditioning species with a longer introduced history, and enemy escape was stronger for distant relatives. In addition, invasive species had a weaker allocation tradeoff than natives. By demonstrating that the net effect of soil biota is more positive for invasive than native and noninvasive introduced species, weakens over time since introduction, and strengthens as phylogenetic distance increasing, we provide mechanistic insights into the considerable role of soil biota in biological invasions, consistent with the predictions of the enemy escape hypothesis. 

This work continues the study of linear error correcting codes against adversarial insertion deletion errors (insdel errors). Previously, the work of Cheng, Guruswami, Haeupler, and Li [Kuan Cheng et al., 2021] showed the existence of asymptotically good linear insdel codes that can correct arbitrarily close to 1 fraction of errors over some constant size alphabet, or achieve rate arbitrarily close to 1/2 even over the binary alphabet. As shown in [Kuan Cheng et al., 2021], these bounds are also the best possible. However, known explicit constructions in [Kuan Cheng et al., 2021], and subsequent improved constructions by Con, Shpilka, and Tamo [Con et al., 2022] all fall short of meeting these bounds. Over any constant size alphabet, they can only achieve rate < 1/8 or correct < 1/4 fraction of errors; over the binary alphabet, they can only achieve rate < 1/1216 or correct < 1/54 fraction of errors. Apparently, previous techniques face inherent barriers to achieve rate better than 1/4 or correct more than 1/2 fraction of errors. In this work we give new constructions of such codes that meet these bounds, namely, asymptotically good linear insdel codes that can correct arbitrarily close to 1 fraction of errors over some constant size alphabet, and binary asymptotically good linear insdel codes that can achieve rate arbitrarily close to 1/2. All our constructions are efficiently encodable and decodable. Our constructions are based on a novel approach of code concatenation, which embeds the index information implicitly into codewords. This significantly differs from previous techniques and may be of independent interest. Finally, we also prove the existence of linear concatenated insdel codes with parameters that match random linear codes, and propose a conjecture about linear insdel codes.